/**
 * @author @xsomnus666_xiawenye★
 * @since 2019/6/20 0020 11:09
 * - Stay Hungry, Stay Foolish
 * - Just do it
 */
public class BST {

    private TreeNode root;
    private int size;


    public BST(int e) {
        root = new TreeNode(e);
        size++;
    }

    public void add(int e) {
        root = add(root, e);
    }

    // 添加某个元素到节点上， 返回添加后的根节点
    private TreeNode add(TreeNode n, int e) {
        if (n == null) {
            size++;
            return new TreeNode(e);
        }
        if (e > n.val) {
            n.right = add(n.right, e);
        } else if (e < n.val) {
            /*if (n.left != null) {
                add(n.left, e);
            } else {
                n.left = new TreeNode(e);
                size++;
            }*/
            n.left = add(n.left, e);
        }
        return n;
    }

    public int preOrder(TreeNode node) {
        int ret = 0;
        if (node == null) {
            return 0;
        } else {
            return node.val + preOrder(node.right) + preOrder(node.left);
        }
    }

    public static void main(String[] args) {
        BST bst = new BST(4);
        bst.add(1);
        bst.add(6);
        bst.add(0);
        bst.add(2);
        bst.add(5);
        bst.add(7);
        bst.add(3);
        bst.add(8);


        System.out.println(bst.preOrder(bst.root.right));
    }
}
